class Solution
{
public:
    int countSteppingNumbers(string low, string high)
    {

        int result = 0;
        auto countSteppingNumbersFromZero = [](string &upper)
        {
            int len = upper.size();
            if (len == 1)
            {
                return upper[0] - '0';
            }

            vector<vector<vector<int>>> dp(len, vector<vector<int>>(10, vector<int>(3, 0)));
            // dp[i][j][diffSign] 表示第i位为j, 且前i位与upper的大小关系为diffSign的个数
            for (int j = 1; j < 10; ++j)
            {
                if (j < upper[0] - '0')
                {
                    dp[0][j][0] = 1;
                }
                else if (j == upper[0] - '0')
                {
                    dp[0][j][1] = 1;
                }
                else
                {
                    dp[0][j][2] = 1;
                }
            }
            int result = 9;

            for (int i = 1; i < len; ++i)
            {
                for (int j = 0; j < 10; ++j)
                {
                    for (int k = 0; k < 10; ++k)
                    {
                        if (abs(j - k) == 1)
                        {
                            if (j < upper[i] - '0')
                            {
                                dp[i][j][0] += dp[i - 1][k][0] + dp[i - 1][k][1];
                                dp[i][j][2] += dp[i - 1][k][2];
                            }
                            else if (j == upper[i] - '0')
                            {
                                dp[i][j][0] += dp[i - 1][k][0];
                                dp[i][j][1] += dp[i - 1][k][1];
                                dp[i][j][2] += dp[i - 1][k][2];
                            }
                            else
                            {
                                dp[i][j][0] += dp[i - 1][k][0];
                                dp[i][j][2] += dp[i - 1][k][1] + dp[i - 1][k][2];
                            }

                            dp[i][j][0] %= 1000000007;
                            dp[i][j][1] %= 1000000007;
                            dp[i][j][2] %= 1000000007;
                        }
                    }
                    if (i == len - 1)
                    {
                        result += dp[i][j][0];
                        result %= 1000000007;
                        result += dp[i][j][1];
                        result %= 1000000007;
                    }
                    else
                    {
                        result += dp[i][j][0];
                        result %= 1000000007;
                        result += dp[i][j][1];
                        result %= 1000000007;
                        result += dp[i][j][2];
                        result %= 1000000007;
                    }
                }
            }

            return result;
        };

        // 将low - 1
        for (int i = low.size() - 1; i >= 0; --i)
        {
            if (low[i] == '0')
            {
                low[i] = '9';
            }
            else
            {
                low[i]--;
                break;
            }
        }

        // cout << countSteppingNumbersFromZero(high) << ", " << countSteppingNumbersFromZero(low) << endl;
        return (countSteppingNumbersFromZero(high) - countSteppingNumbersFromZero(low) + 1000000007) % 1000000007;
    }
};